package BiTree;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: java_concurrent
 * @description: 求两个节点的最近公共祖先
 * @author: lxf
 * @create: 2024-07-15 17:01
 **/
public class LowestCommonAncestor {


    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(8, null, null);
        TreeNode node6 = new TreeNode(4);
        TreeNode node5 = new TreeNode(2, new TreeNode(7), node6);
        TreeNode node4 = new TreeNode(6, null, null);
        TreeNode node3 = new TreeNode(1, new TreeNode(0), node7);
        TreeNode node2 = new TreeNode(5, node4, node5);
        TreeNode node1 = new TreeNode(3, node2, node3);
        TreeNode node = lowestCommonAncestor(node1, node2, node3);
        System.out.println(node.val);
    }

    // 从下往上遍历，以此取该节点的左子树集合与右子树集合，判断所给节点在局部与该节点与左子树集合与右子树集合之间的关系
    // 如果p，q各在一边 或者 该节点为p/q，另一个在任意集合中 返回该节点
    static TreeNode tmp = null;

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        lowestCommonAncestor(root.left, p, q);
        lowestCommonAncestor(root.right, p, q);
        List<TreeNode> lefts = new ArrayList<>();
        List<TreeNode> rights = new ArrayList<>();
        lowestCommonAncestor2(root.left, lefts);
        lowestCommonAncestor2(root.right, rights);
        if ((lefts.contains(p) && rights.contains(q)) ||
                (rights.contains(p) && lefts.contains(q)) ||
                (root == p && lefts.contains(q)) ||
                (root == p && rights.contains(q)) ||
                (root == q && lefts.contains(p)) ||
                (root == q && rights.contains(p))
        ) {
            tmp = root;
        }
        return tmp;
    }

    public static void lowestCommonAncestor2(TreeNode root, List<TreeNode> nodes) {
        if (root == null) {
            return;
        }
        nodes.add(root);
        lowestCommonAncestor2(root.left, nodes);
        lowestCommonAncestor2(root.right, nodes);
    }
}
